#include<iostream>
#include<map>
using namespace std;
template<class key, class val>
struct treenode {
	treenode<key,val>*_parent;
	treenode<key,val>*_left;
	treenode<key,val>*_right;
	int _balance;
	pair<key,val> _key;
	treenode(const pair<key,val>& a)
		:_parent(nullptr)
		,_left(nullptr)
		, _right(nullptr)
		, _balance(0)
		,_key(a)
	{}
};
template<class K, class V>
class avltree {
public:
	typedef treenode<K, V> Node;
	bool insert(const pair<K, V>& key)
	{
		if (_root ==nullptr)
		{
			_root = new Node(key);
			return true;
		}
		Node* cur = _root;
		Node* parent = _root;
		while (cur)
		{
			if (cur->_key.first > key.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key.first < key.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
				return false;
		}
		cur = new Node(key);
		if (parent->_key.first > key.first)
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else if (parent->_key.first < key.first)
		{
			parent->_right = cur;
			cur->_parent =parent;
		}
		while (parent)
		{
			if (parent->_right == cur)
			{
				parent->_balance++;	
			}
			else if (parent->_left == cur)
			{
				parent->_balance--;
			}
			if (parent->_balance == 0)
			{
				break;
			}
			else if (parent->_balance == 1 || parent->_balance == -1)
			{
				cur = parent;
				parent = parent->_parent;
				
			}
			else if (parent->_balance == 2 || parent->_balance == -2)
			{
				if (parent->_balance == 2)
				{
					if (cur->_balance == 1)
					{
						reverseleft(parent);
					}
					else if (cur->_balance == -1)
					{
						revserrl(parent);
					}
				}
				else if (parent->_balance == -2)
				{
					if (cur->_balance == -1)
					{
						_reverseright(parent);
					}
					else if (cur->_balance == 1)
					{
						reverselr(parent);

					}
				}

			}
		}
	 }
	 void _reverseright(Node* parent)
	 {
		 Node* pre = parent->_parent;
		 Node* subleft = parent->_left;
		 Node* subleftright = subleft->_right;
		 parent->_left= subleft->_right;
		 subleft->_right = parent;
		 subleft->_parent = pre;
		 parent->_parent = subleft;
		 if (subleftright)
		subleftright->_parent = parent;
		 if (pre == nullptr)
		 {
			 _root = subleft;
			 subleft->_parent = nullptr;
		 }
		 else
		 {
			 if (pre->_right == parent)
				 pre->_right = subleft;
			 else
				 pre->_left = subleft;
		 }
		 subleft->_balance = parent->_balance = 0;
	 }
	 void reverseleft(Node* parent)
	 {
		 Node* subright = parent->_right;
		 Node* pre = parent->_parent;
		 Node* subrightleft = subright->_left;
		 parent->_right = subrightleft;
		 if (subrightleft)
		subrightleft->_parent = parent;
		 subright->_left = parent;
		 parent->_parent = subright;
		 subright->_parent = pre;
		 if (pre ==nullptr)
		 {
			 _root = subright;
			 subright->_parent = nullptr;
		 }
		 else
		 {
			 if (pre->_left == parent)
				 pre->_left = subright;
			 else
				 pre->_right = subright;
		 }
		 parent->_balance = subright->_balance = 0;
	 }
	 void revserrl(Node* parent)
	 {
		 Node* subr = parent->_right;
		 Node* subrleft = subr->_left;
		 int balance = subrleft->_balance;
		 _reverseright(parent->_right);
		 reverseleft(parent);
		 if (balance == -1)
		 {
			 parent->_balance = 0;
			 subr->_balance = 1;
			subrleft->_balance = 0;
		 }
		 else if (balance == 1)
		 {
			 parent->_balance = -1;
			 subr->_balance = 0;
			 subrleft->_balance = 0;
		 }
		 else if (balance==0)
		 {
			 parent->_balance = 0;
			 subr->_balance = 0;
			 subrleft->_balance = 0;
		 }
		 
	 }
	 void reverselr(Node*parent)
	 {
		 Node* subl = parent->_left;
		 Node* sublr = subl->_right;
		 int balance = sublr->_balance;
		 reverseleft(subl);
		 _reverseright(parent);
		 if (balance == 1)
		 {
			 parent->_balance = 0;
			 subl->_balance = -1;
			 sublr->_balance = 0;
		 }
		 else if (balance == -1)
		 {
			 parent->_balance = 1;
			 subl->_balance = 0;
			 sublr->_balance = 0;
		 }
		 else if (balance == 0)
		 {
			 parent->_balance = 0;
			 subl->_balance = 0;
			 sublr->_balance = 0;
		 }
	 }
	 void find(Node* p)
	 {
		 if (p == nullptr)
		 {
			 return;
		 }
		 find(p->_left);
		 cout << p->_key.first << " " << p->_key.first << endl;
		 find(p->_right);
	}
	 void _find()
	 {
		 find(_root);
		} 
	 int Hei(Node* root)
	 {
		 if (root == nullptr)
			 return 0;
		 int lefhight = Hei(root->_left);
		 int righight = Hei(root->_right);

		 return lefhight > righight ? lefhight + 1 : righight + 1;
	 }
	 bool isbalance(Node* root)
	 {
		 if (root == nullptr)
			 return true;
		 int lefhight = Hei(root->_left);
		 int righight = Hei(root->_right);
		 return abs(lefhight-righight)<2
			 &&isbalance(root->_left)
			 &&isbalance(root->_right);
	 }
	bool _isbalance()
	 {
		 isbalance(_root);
		 return true;
	 }
private:
	Node* _root = nullptr;
};

void tree()
{
	/*int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };*/
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	avltree<int, int> c;
	for (auto e : a)
	{
		c.insert(make_pair(e, e));
	}
	c._find();
	cout << c._isbalance() << endl;
}
int main()
{
	tree();

	return 0;
}











































